package main

import "fmt"

//#link: https://leetcode-cn.com/problems/make-the-xor-of-all-segments-equal-to-zero/
func main() {
	nums := []int{1, 2, 0, 3, 0}
	k := 1
	fmt.Println(minChanges(nums, k))
}

//参考的三叶的题解: https://leetcode-cn.com/problems/make-the-xor-of-all-segments-equal-to-zero/solution/gong-shui-san-xie-chou-xiang-cheng-er-we-ww79/
func minChanges(nums []int, k int) int {
	n, max := len(nums), 1024
	dp := make([][]int, k)
	g := make([]int, k)
	for i := range dp {
		dp[i] = make([]int, max)
		for j := range dp[i] {
			dp[i][j] = 1 << 31
		}
		g[i] = 1 << 31
	}
	//k列
	for i := 0; i < k; i++ {
		tempMap := make(map[int]int)
		total := 0
		for j := i; j < n; j += k {
			tempMap[nums[j]]++
			total++
		}
		//第一行的时候
		if i == 0 {
			for xor := 0; xor < max; xor++ {
				if value, ok := tempMap[xor]; ok {
					dp[0][xor] = min(dp[0][xor], total-value)
				} else {
					dp[0][xor] = min(dp[0][xor], total)
				}
				g[i] = min(g[i], dp[0][xor])
			}
		} else {
			for xor := 0; xor < max; xor++ {
				//整列替换
				dp[i][xor] = g[i-1] + total
				//部分替换
				for cur, _ := range tempMap {
					if value, ok := tempMap[xor^cur]; ok {
						dp[i][xor] = min(dp[i][xor^cur], dp[i-1][xor^cur]+total-value)
					} else {
						dp[i][xor] = min(dp[i][xor], dp[i-1][xor^cur]+total)
					}
				}
				g[i] = min(g[i], dp[i][xor])
			}
		}

	}
	return dp[k-1][0]
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
